import java.awt.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

public class project {
    public int eraseOverlapIntervals(int[][] intervals) {
        int len=intervals.length;
        if(len==0){
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int ret=0;
        int right=intervals[0][1];
        for(int i=1;i<len;i++){
            if(intervals[i][0]>=right){
                right=intervals[i][1];
                ret++;
            }
        }
        return len-ret-1;
    }
















    public double minAreaFreeRect(int[][] points) {
        int row=points.length;
        Point[] arr=new Point[row];
        Set<Point> set=new HashSet<>();
        double ret=Double.MAX_VALUE;
        for(int i=0;i<row;i++){
            arr[i]=new Point(points[i][0],points[i][1]);
            set.add(arr[i]);
        }
        for(int i=0;i<row;i++){
            Point p1=arr[i];
            for(int j=0;j<row;j++){
                if(i!=j){
                    Point p2=arr[j];
                    for(int k=j+1;k<row;k++){
                        if(i!=k){
                            Point p3=arr[k];
                            Point p4=new Point(p2.x+p3.x-p1.x,p2.y+p3.y-p1.y);
                            if(set.contains(p4)){
                                int index=((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y));
                                if(index==0){
                                    ret=Math.min(ret,p1.distance(p2)*p1.distance(p3));
                                }
                            }
                        }
                    }
                }
            }
        }
        return ret==Double.MAX_VALUE?0:ret;
    }













    public boolean searchMatrix(int[][] matrix, int target) {
        int row=matrix.length;
        int col=matrix[0].length;
        int x=0;
        int y=col-1;
        while (x<row&&y>=0){
            int value=matrix[x][y];
            if(value>target){
                y--;
            }else if(value<target){
                x++;
            }else{
                return true;
            }
        }
        return false;
    }



















    public int minimumLengthEncoding(String[] words) {
        Set<String> set=new HashSet<>(Arrays.asList(words));
        for(String s:words){
            for(int i=1;i<s.length();i++){
                set.remove(s.substring(i));
            }
        }
        int len=0;
        for(String s:set){
            len+=s.length()+1;
        }
        return len;
    }


















    public int findTheWinner(int n, int k) {
        if(n==1){
            return 1;
        }
        int ret=findTheWinner(n-1,k)+k;
        return ret%n==0?0:ret%n;
    }
}
